package stack;
    /*
    155. 最小栈
    设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
    实现 MinStack 类:
    MinStack() 初始化堆栈对象。
    void push(int val) 将元素val推入堆栈。
    void pop() 删除堆栈顶部的元素。
    int top() 获取堆栈顶部的元素。
    int getMin() 获取堆栈中的最小元素。
    */
import java.util.Stack;
class MinStack {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    public MinStack() {

    }
    //入栈
    public void push(int val) {
        //空栈时，将val都入两个栈
        if(stack.isEmpty()){
            stack.push(val);
            minStack.push(val);
            return;
        }
        stack.push(val);
        int top = minStack.peek();
        if(top < val){
            minStack.push(top);
        }else{
            minStack.push(val);
        }
    }
    //出栈
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    //获取栈顶元素
    public int top() {
        return stack.peek();
    }
    //获取栈中最小的元素
    public int getMin() {
        return minStack.peek();
    }
}
public class practice_3_16 {
    /*
    * 20. 有效的括号
    *给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
    *有效字符串需满足：左括号必须用相同类型的右括号闭合。
    *               左括号必须以正确的顺序闭合。
    *               每个右括号都有一个对应的相同类型的左括号。
    */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            //左括号直接入栈
            if(c == '(' || c == '{' || c == '['){
                stack.push(c);
            }else{  //右括号
                //栈为空，说明没有与右括号匹配的左括号，返回false
                if(stack.isEmpty()){
                    return false;
                }
                //取出左括号
                char ch = stack.pop();
                //右括号为小括号，左括号不是小括号，返回false
                if(c == ')' && ch != '('){
                    return false;
                }
                //右括号为大括号，左括号不是大括号，返回false
                if(c == '}' && ch != '{'){
                    return false;
                }
                //右括号为中括号，左括号不是中括号，返回false
                if(c == ']' && ch != '['){
                    return false;
                }
            }
        }
        //栈为空，则括号均匹配，返回true
        if(stack.isEmpty()){
            return true;
        }else{  //栈非空，则存在未匹配的左括号，返回false
            return false;
        }
    }
    /*
    * JZ31 栈的压入、弹出序列
    * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
    * 假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是
    * 该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
    * 1. 0<=pushV.length == popV.length <=1000
    * 2. -1000<=pushV[i]<=1000
    * 3. pushV 的所有数字均不相同
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int pushPos = 0, popPos = 0;
        for(pushPos = 0; pushPos < pushV.length; pushPos++){
            //将入栈数组的元素入栈
            stack.push(pushV[pushPos]);
            //栈非空，且栈顶元素等于popV[popPos]
            while(!stack.isEmpty() && popV[popPos] == stack.peek()){
                popPos++;   //出栈数组后移一位
                stack.pop();    //出栈
            }
        }
        //栈为空，说明入栈顺序和出栈顺序匹配，返回true,否则返回false
        if(stack.isEmpty()){
            return true;
        }else{
            return false;
        }
    }

    /*
    * 150. 逆波兰表达式求值
    给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
    请你计算该表达式。返回一个表示表达式值的整数。
    注意：
    有效的算符为 '+'、'-'、'*' 和 '/' 。
    每个操作数（运算对象）都可以是一个整数或者另一个表达式。
    两个整数之间的除法总是 向零截断 。
    表达式中不含除零运算。
    输入是一个根据逆波兰表示法表示的算术表达式。
    答案及所有中间计算结果可以用 32 位 整数表示。
    */
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        String str = "+-*/";
        for(String s : tokens){
            //s不是运算符，则为数字字符串，将数字字符串转为整数后入栈
            if(!str.contains(s)){
                stack.push(Integer.parseInt(s));
            }else{
                //s是运算符，取出栈顶的两个数进行运输
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch(s){
                    //s是加号
                    case "+" :
                        stack.push(num1 + num2);
                        break;
                    //s是减号
                    case "-" :
                        stack.push(num1 - num2);
                        break;
                    //s是乘号
                    case "*" :
                        stack.push(num1 * num2);
                        break;
                    //s是除号
                    case "/" :
                        stack.push(num1 / num2);
                        break;
                    default :
                        break;
                }
            }

        }
        //返回栈顶元素
        return stack.peek();
    }
    public static void main(String[] args) {
        System.out.println();
        String s = "123";

        System.out.println(Integer.parseInt(s));

    }
}
